package linkedList.迭代;

import linkedList.BaseLinkedListTest;
import po.ListNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 对链表进行插入排序147.java
 * @Description TODO https://leetcode-cn.com/problems/insertion-sort-list/
 * 给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
 *
 * 插入排序 算法的步骤:
 *
 * 1.插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
 * 2.每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
 * 3.重复直到所有输入数据插入完为止。
 *
 * @createTime 2021年03月12日 13:53:00
 */
public class 对链表进行插入排序147 extends BaseLinkedListTest {

    public static ListNode insertionSortList(ListNode head)   {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode pre = new ListNode(-1, head);
        //todo 两个指针一个表示当前头 一个表示下一个节点  4-->2--->1 其中cur为4  curNext为2
        ListNode cur = head,curNext = head.next,tempPre=pre, temp = null;

        while (curNext != null) {
            //todo 临时节点用来存，要交换节点中后一个节点的下一个节点 4-->2--->1 其中temp为1
            temp = curNext.next;
            if (curNext.val < cur.val) {
                //todo 每次循环开始都需要从pre的第一个节点开始
                tempPre=pre;
                //todo 找到顺序链表中大小最大但是比下一个加入的数字小的节点
                while (tempPre.next.val<=curNext.val){
                    tempPre=tempPre.next;
                }
                cur.next=temp;
                curNext.next = tempPre.next;
                tempPre.next=curNext;
            }else {
                cur=cur.next;
            }
            curNext=temp;
        }
        return pre.next;
    }

    public static void main(String[] args) {
        ListNode listNode = insertionSortList(createLinkedList(-1,5,3,4,0));
        System.out.println(listNode);
    }
}
